package lc;

import org.junit.Test;

public class Ex678 {
    class Solution {
        /**
         * 为什么先出栈(是正确的 即使这个)实际匹配的是(
            对于)多的情况，(和*实际上是等价的。
         */
        public boolean checkValidString(String s) {
            int n = s.length();
            int[] left = new int[n];
            int[] star = new int[n];
            char[] cs = s.toCharArray();
            int i = -1, k = -1;
            for (int j = 0; j < star.length; j++) {
                char c = cs[j];
                if (c == '(') {
                    left[++i] = j;
                } else if (c == '*'){
                    star[++k] = j;
                } else {
                    if (i < 0) {
                        if (k < 0) {
                            return false;
                        } else {
                            k--; //其次*出栈
                        }
                    } else {
                        i--; //优先(出栈
                    }
                }
            }
            if (i > k) {
                return false;
            }
            while (i >= 0) { 
                if (left[i] < star[k]) { //必须保证(在)的左边。
                    i--;
                    k--;
                } else {
                    return false;
                }
            }
            return true;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.checkValidString("(((**(*)))(*)"));
    }
}
